package com.c2b.algorithm.newcoder;

/**
 * <a href='https://www.nowcoder.com/practice/253d2c59ec3e4bc68da16833f79a38e4?tpId=295&tqId=23286&ru=%2Fexam%2Foj&qru=%2Fta%2Fformat-top101%2Fquestion-ranking&sourceUrl=%2Fexam%2Foj'>BM7 链表中环的入口结点</a>
 *
 * @author c2b
 * @since 2024/3/14 10:39
 */
public class BM7EntryNodeOfLoop {
    public static class Solution {
        public ListNode EntryNodeOfLoop(ListNode pHead) {
            if (pHead == null || pHead.next == null) {
                return null;
            }
            ListNode slow = pHead;
            ListNode fast = pHead;
            while (fast != null && fast.next != null) {
                slow = slow.next;
                fast = fast.next.next;
                if (slow == fast) {
                    fast = pHead;
                    while (slow != fast) {
                        slow = slow.next;
                        fast = fast.next;
                    }
                    return slow;
                }
            }
            return null;
        }
    }
}
